package com.yan_jiu_sheng.daily.AC;

/**
 * https://leetcode.cn/problems/subtree-of-another-tree/description/?envType=daily-question&envId=2024-08-04
 * 参考通过
 *
 * @author yulongtian
 * @create 2024-08-04 9:52
 */
public class Test20240804 {
    public static void main(String[] args) {

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 笨方法，嵌套暴力递归。遍历root枚举与sub同值的节点node(若不同值则递归判断root左右子树)，
     * 对每个node子树再进一步递归对比与sub是否相等。
     *
     * @param root
     * @param subRoot
     * @return
     */
// 嵌套暴力递归
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 按节点数范围sub不为空，root为空直接跳过。
        if (root == null) return false;
        // 合法条件：同值且子树相同。
        if (root.val == subRoot.val && dfs(root, subRoot)) {
            return true;
        }
        // root不是sub同值节点，递归判断root左右子树。
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    // 递归判断两棵树相等
    public boolean dfs(TreeNode node, TreeNode sub) {
        if (node == null || sub == null) {
            return node == sub;
        }
        if (node.val != sub.val) {
            return false;
        }
        return dfs(node.left, sub.left) && dfs(node.right, sub.right);
    }


}
